package com.faiz.algorithm;

public class ReverseListNode {
    // 迭代翻转链表（头插法）
    private ListNode reverseList(ListNode head) {
        // 构造哑节点
        ListNode dummy = new ListNode(555);
        dummy.next = head;
        ListNode g = dummy, p = head;

        while (head.next != null) {
            ListNode remove = head.next;
            head.next = head.next.next;

            remove.next = dummy.next;
            dummy.next = remove;
        }
        return dummy.next;
    }

    // 迭代翻转
    private ListNode reverseList1(ListNode head) {
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head;
        while (cur != null) {
            nxt = cur.next;
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }

}
